package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 括号生成
 *
 * @author winson
 * @create 2022-03-30 11:32
 */
public class GenerateParenthesisSolution {

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        backTrack(list, new StringBuilder(), 0, 0, n);
        return list;
    }

    /**
     * 在序列仍然保持有效时才添加 '(' or ')'
     * 如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
     * @param list
     * @param stringBuilder
     * @param left
     * @param right
     * @param max
     */
    public void backTrack(List<String> list, StringBuilder stringBuilder, int left, int right, int max) {
        if (stringBuilder.length() == 2 * max) {
            list.add(stringBuilder.toString());
            return;
        }
        if (left < max) {
            stringBuilder.append('(');
            backTrack(list, stringBuilder, left + 1, right, max);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
        if (right < left) {
            stringBuilder.append(')');
            backTrack(list, stringBuilder, left, right + 1, max);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
    }
}
